Video âm nhạc "Rehab" lấy bối cảnh ở công viên Vasquez Rocks Park (ảnh), phía ngoài thành phố Los Angeles.

Rihanna đã ghi hình một video âm nhạc cho ca khúc cùng với Justin Timberlake tại công viên Vasquez Rocks Park phía ngoài thành phố Los Angeles vào ngày 22 tháng 10 năm 2008.[32] Video do Anthony Mandler đạo diễn, anh là người trước đó đã từng đóng vai trò tương tự trong các video âm nhạc của nữ ca sĩ như "Take a Bow" và "Disturbia".[33] Những hình ảnh hậu trường của video cũng được phát tán trên mạng cùng ngày.[34] Tim Nixon đến từ báo The Sun đã viết rằng "chất xúc tác đỏ rực nồng nàn" giữa Rihanna và Justin Timberlake trước đó là một thứ rất khó để cho các cặp đôi có thể cảm nhận được.[35] Simon Reynolds từ trang Digital Spy đã nói rằng người tình lúc bấy giờ của Timberlake, Jessica Biel, "được cho là 'ngán đến tận cổ' khi thấy cảnh Rihanna mặc một bộ đồ mát mẻ khi quay phim cùng Justin Timberlake."[36] Video được ra mắt vào ngày 17 tháng 11 năm 2008, trên kênh MTV.[37]

Timberlake kể lại với chương trình tin tức về ngành giải trí Access Hollywood:

"Tôi đóng vai người tình cũ trong đoạn video ấy, vì thế nên tôi phải cho khán giả thấy được sự bấp bênh trong mối quan hệ của chúng tôi. Nhưng thay vào đó thì chúng tôi đã có một khoảng thời gian tuyệt vời vì gần như bất cứ lúc nào chúng tôi cũng có thể đùa giỡn quanh khu vực phim trường được."[38]

Các cảnh quay khác nhau trong video, bao gồm cảnh Rihanna đứng dựa người vào một chiếc xe mui trần giữa nơi sa mạc vào ban ngày (trên) và cảnh Rihanna và Timberlake yên vị bên cạnh một chiếc "ngôi nhà di động" vào ban đêm (dưới).

Video bắt đầu với cảnh Rihanna mặc bộ trang phục khá mát mẻ có họa tiết như lưới đánh cá, đứng dựa người vào một chiếc xe mui trần tại sa mạc. Timberlake, khoác lên mình một chiếc áo khoác tối màu và một chiếc quần bò, lái một chiếc xe mô tô tiến gần lại nơi Rihanna đứng. Khi tới nơi, anh cởi bỏ chiếc áo khoác nặng nề của mình và đứng "tắm" dưới dòng nước nhuộm hồng trước khi gửi lời chào đến Rihanna, khi ấy đang đứng bên cạnh "ngôi nhà di động" hãng Airstream của mình.[39] Sau màn chào hỏi, cặp đôi trườn lên mui trước của chiếc xe ô tô loại cũ lúc trước và quấn quýt lấy nhau. Trong suốt đoạn video, khán giả có thể thấy được Rihanna và Timberlake tạo nhiều kiểu dáng khác nhau, từ gợi cảm cho đến "phòng thủ".[34] David Balls của trang Digital Spy nhận xét: "Cặp đôi ca sĩ nhạc pop đã thể hiện vai diễn của mình một cách đầy mãnh liệt và khêu gợi mà chẳng tốn nhiều công sức. Chẳng có gì ngạc nhiên khi biết rằng người phụ nữ của Timberlake lại có một cảm giác còn trên cả tuyệt vời."[39] Tim Nixon từ báo The Sun thì lại viết "Hình ảnh của một Rihanna gợi cảm—mặc trên người một loạt những bộ trang phục như đang trêu ngươi người xem—"quằn quại" cùng với Justin thật đúng là một bữa tiệc chiêu đãi."[35] Trong cuốn sách Post Cinematic Affect xuất bản năm 2010 của mình, Steven Shaviro đã viết: "Trong các video âm nhạc "Rehab", "Love Sex Magic" và 4 Minutes", Timberlake đã "tỏa ra một làn nhiệt gợi dục", và những video âm nhạc trên "có thể được đối chiếu với các video âm nhạc của các bài hát trích từ album Future Sex/Love Sounds của Timberlake, có thể được giáo sư nổi tiếng Joshua Clover mô tả mang tính thuyết phục là một sự đổi chác "thân hữu" giữa Timberlake và nhà sản xuất thu âm thân thuộc với nam ca sĩ, Timbaland".[40] Video đã giành giải Video âm nhạc xuất sắc nhất tại Giải Urban Music Awards 2009 tại Mỹ.[41]